Nati Linial

Nathan (Nati) Linial (born 1953 in Haifa, Israel)^[1] is an Israeli mathematician and computer scientist, a professor in the Rachel and Selim Benin School of Computer Science and Engineering at the Hebrew University of Jerusalem,^[2] and an ISI highly cited researcher.^[3]

Linial did his undergraduate studies at the Technion, and received his Ph.D. in 1978 from the Hebrew University under the supervision of Micha Perles.^[1][4] He was a postgraduate researcher at the University of California, Los Angeles before returning to the Hebrew University as a faculty member.^[1]

Selected publications

• Borodin, Allan; Linial, Nathan; Saks, Michael E. (1992), "An optimal on-line algorithm for metrical task system", J. ACM 39 (4): 745–763, doi:10.1145/146585.146588 . This paper on competitive analysis of online algorithms studies metrical task systems, a very general model of tasks where decisions on how to service a sequence of requests must be made without knowledge of future requests. It introduces the metrical task system model, describes how to use it to model various scheduling problems, and develops an algorithm that in many situations can be shown to perform optimally.
• Linial, Nathan; Mansour, Yishay; Nisan, Noam (1993), "Constant depth circuits, Fourier transform, and learnability", J. ACM 40 (3): 607–620, doi:10.1145/174130.174138 . By performing harmonic analysis on functions in the complexity class AC⁰ (a class representing highly parallelizable computational problems), Linial and his co-authors show that these functions behave poorly as pseudorandom number generators, can be approximated well by polynomials, and can be learned efficiently by machine learning systems.
• Linial, Nathan; London, Eran; Rabinovich, Yuri (1995), "The geometry of graphs and some of its algorithmic applications", Combinatorica 15 (2): 215–245, doi:10.1007/BF01200757 . Linial's most-cited paper according to Google scholar, this paper explores connections between graph-theoretic problems such as the multi-commodity flow problem and low-distortion embeddings of metric spaces into low-dimensional spaces such as those given by the Johnson–Lindenstrauss lemma.
• Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications", Bulletin of the American Mathematical Society 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8, MR2247919 . In 2008 Linial and his co-authors won the Levi L. Conant Prize of the American Mathematical Society for best mathematical exposition for this article, a survey on expander graphs.^[1]

References